public class Test1 {
    //leetcode 10 正则表达式匹配
    public boolean isMatch(String ss, String pp) {
        //dp[i][j]表示s串[0,i]之间的子串和p串[0,j]子串是否匹配
        //状态转移方程：
        //当p[j]=='.'时，dp[i][j] = dp[i-1][j-1]
        //当dp[j]=='*'时，有两种情况：
        //当p[j-1]为字母的时候dp[i][j] = dp[i][j-1] || (s[i] == p[j-1] && dp[i-1][j-2]) || (s[i-1] == p[i-1] && dp[i-2][j-2])...
        //dp[i-1][j] = dp[i-1][j-1] || (s[i-1] == p[j-1] && dp[i-2][j-2])...
        //当p[j-1]为*的时候dp[i][j] = dp[i][j-2] || dp[i-1][j]
        int m = ss.length(), n = pp.length();
        boolean[][] dp = new boolean[m+1][n+1];
        ss = " " + ss;
        pp = " " + pp;
        char[] s = ss.toCharArray(), p = pp.toCharArray();
        //初始化，当s串为空串的时候，只有当p串为 nx字母* 或者 nx.*的情况才能够匹配，其他情况都为false
        //而当p为空串的时候，之后当s串也为空串的时候才可以匹配，也就是dp[0][0]=true
        dp[0][0] = true;
        for (int i = 2; i <= n; i+=2) {
            if (p[i] == '*') dp[0][i] = true;
            else break;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j] == '.') {
                    dp[i][j] = dp[i-1][j-1];
                }else if (p[j] == '*') {
                    if (p[j-1] == '.') {
                        dp[i][j] = dp[i][j-2] || dp[i-1][j];
                    }else {
                        dp[i][j] = dp[i][j-2] || (s[i] == p[j-1] && dp[i-1][j]);
                    }
                }else {
                    dp[i][j] = s[i] == p[j] && dp[i-1][j-1];
                }
            }
        }
        return dp[m][n];
    }
}
